import java.util.Arrays;

public class Leetcode {
}

//leetcode:673:最长递增子序列的个数
class Solution1 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;

        //创建两个表分别代表以i位置为结尾的最长递增子序列的长度和个数
        int[] len = new int[n];
        int[] cnt = new int[n];

        //由于单个元素也为子序列，所以我将所有位置初始化为1
        for(int i = 0; i < n; i++){
            len[i] = cnt[i] = 1;
        }

        int ret = 1, count = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                //由于示要递增的所以我们要找的值要比i位置小
                if(nums[j] < nums[i]){
                    //如果这个j位置的最长子序列长度加上1后与i位置相等，就说明以i位置为结尾的最长子序列个数又多了，因此我们要让个数加上j位置的个数
                    if(len[j] + 1 == len[i]) cnt[i] += cnt[j];
                    //如果长度大于了i位置的长度，那么就代表以i位置为结尾的最长递增子序列为此时的长度
                    if(len[j] + 1 > len[i]){
                        //所以我们要更新个数和长度
                        cnt[i] = cnt[j];
                        len[i] = len[j] + 1;
                    }
                }
            }
            //如果长度与原本相同，就代表以这个长度为最长的递增子序列个数又增多了，需要加上
            if(ret == len[i]) count += cnt[i];
                //如果大于了原本长度，就代表此时的长度才为新的最长长度
            else if(ret < len[i]){
                //所以更新新的长度和个数
                ret = len[i];
                count = cnt[i];
            }
        }
        //最后返回最后的最长长度的个数
        return count;
    }
}

//leetcode:646:最长数对链
class Solution2 {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        //将二维数组按照第一个值进行排序
        Arrays.sort(pairs,(a, b) -> a[0] - b[0]);
        int[] dp = new int[n];
        //由于每个数对都可以作为序列，所以将每个位置初始化为1
        for(int i = 0;i < n; i++){
            dp[i] = 1;
        }

        int ret = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                //如果前一个数对的第二个值是小于i位置的数对的第一个值的
                if(pairs[j][1] < pairs[i][0]){
                    //那么我们就判断此时数对链的的长度和j位置的长度加上此时i位置后那个更长
                    dp[i] = Math.max(dp[i] , dp[j] + 1);
                }
            }
            //得到所有位置的最长链
            ret = Math.max(ret,dp[i]);
        }
        return ret;
    }
}